#ifndef COMPACTGRAPHTMPL_H_
#define COMPACTGRAPHTMPL_H_

#include "graph_support/impls/BaseGraphTmpl.h"

#include <vector>

#include <boost/pool/object_pool.hpp>

#include "graph_support/attributes/LengthEdgeAttributes.h"
#include "graph_support/impls/WrapEdgeIterator.h"
#include "graph_support/utils/PtrAccessOpSimulator.h"


namespace GRAPH_SUPPORT_NS
{
namespace impls
{
namespace compact
{

template <
			typename VertexT = int,
			typename EdgeAttributesT = attributes::Length1EdgeAttributes,
			typename HashFn = stdext::hash< VertexT >,
			typename CmpFn = stdext::equal_to< VertexT >, // compares VertexT - s
			typename VertNumResolver = utils::ResolveTableHash< VertexT, size_t, HashFn, CmpFn >
			>
class CompactGraphTmpl : public BaseGraphTmpl< VertexT, HashFn, CmpFn, VertNumResolver >
{
private: // TODO: move down
	typedef BaseGraphTmpl< VertexT, HashFn, CmpFn, VertNumResolver > Super;
	typedef CompactGraphTmpl< VertexT, EdgeAttributesT, HashFn, CmpFn, VertNumResolver > MyT;
public:
	typedef VertexT GrVertex;
	typedef EdgeAttributesT EdgeAttributes;
private:
	typedef typename IGraph::EdgeAttributesImpl< EdgeAttributes >::IAttributes IEdgeAttributes;
//	typedef typename IGraph::EdgeAttributesImpl< EdgeAttributes >::Attributes IEdgeAttributesImpl;
public:
	class GrEdge : public Graph::GrEdge
	{
	public:
		GrEdge( MyT & gr, size_t begVid, size_t edgePos )
			: gr( & gr )
			, begVid( begVid )
			, edgePos( edgePos )
		{
		}
		GrEdge()
			: gr( NULL )
			, begVid( Graph::NOT_A_VERTEX_ID )
			, edgePos( Graph::NOT_A_VERTEX_ID )
		{
		}
		const GrVertex beg() const
		{
			return gr->num2vert( begVid );
		}
		const GrVertex end() const
		{
			return gr->getVertices()[gr->dest[edgePos]];
		}
		size_t begId() const
		{
			return begVid;
		}
		// TODO: add const for beg/edn - Id ()
		size_t endId() const
		{
			return gr->dest[edgePos];
		}
// TODO: base edge
	public:
		EdgeAttributes & getAttributes()
		{
			return * gr->attributes[edgePos];
		}
	public:
		bool operator == ( const GrEdge & that ) const
		{
			return this->gr == that.gr && this->begVid == that.begVid && this->edgePos == that.edgePos;
		}
	private:
		MyT * gr;
		size_t begVid;
		size_t edgePos;
	};
	typedef utils::PtrAccessOpSimulator< GrEdge > GrEdgePtr;
	class EdgeIterator
	{
	public:
		typedef int difference_type;
		typedef GrEdgePtr value_type;
		typedef GrEdgePtr * pointer;
		typedef GrEdgePtr & reference;
		typedef std::forward_iterator_tag iterator_category;
	public:
		EdgeIterator( MyT & gr, int edgePos, size_t begVid )
			: gr( & gr )
			, edgePos( edgePos )
			, begVid( begVid )
		{
		}
		const EdgeIterator & operator ++ ()
		{
			assert( edgePos < gr->nxBuf.size() );
			edgePos = gr->nx[edgePos];
			return * this;
		}
		bool operator != ( const EdgeIterator & that ) const
		{
			return this->edgePos != that.edgePos;
		}
		bool operator == ( const EdgeIterator & that ) const
		{
			return this->edgePos == that.edgePos;
		}
		GrEdgePtr operator * ()
		{
			return GrEdgePtr( GrEdge( * gr, begVid, edgePos ) );
		}
		GrEdgePtr * operator -> ()
		{
			return NULL;
		}
	private:
		MyT * gr;
		int edgePos;
		size_t begVid; // TODO: review int <--> size_t
	};

public:
	template< typename IterT >
	CompactGraphTmpl( IterT verticesBeg, IterT verticesEnd, bool isBidirected = false )
		: Super( verticesBeg, verticesEnd, isBidirected )
	{
		init();
	}

	template< typename CollT >
	CompactGraphTmpl( const CollT & vertsColl, bool isBidirected = false )
		: Super( vertsColl.begin(), vertsColl.end(), isBidirected )
	{
		init();
	}


public:
	EdgeIterator getEdgsBeg( const GrVertex & v )
	{
		size_t vid = vert2num( v );
		return EdgeIterator( * this, st[vid], vid );
	}

	EdgeIterator getEdgsEnd( const GrVertex & v )
	{
		size_t vid = vert2num( v );
		return EdgeIterator( * this, -1, vid );
	}

	EdgeIterator getEdgsBegId( size_t vid )
	{
		return EdgeIterator( * this, st[vid], vid );
	}

	EdgeIterator getEdgsEndId( size_t vid )
	{
		return EdgeIterator( * this, -1, vid );
	}

	template< typename FnT >
	void forEachOutEdge( GrVertex v, const FnT & fn )
	{
		forEachOutEdgeId( Super::vert2num( v ), fn );
	}

	template< typename FnT >
	void forEachOutEdgeId( size_t vid, const FnT & fn )
	{
		// TODO: proper implementation
		Super::checkVIDValid( vid );
		std::for_each( getEdgsBegId( vid ), getEdgsEndId( vid ),
				boost::bind( fn, boost::bind( & utils::ptr2ref< GrEdge, GrEdgePtr >, _1 ) ) );
	}

	virtual IGraph::IEdgeIteratorPtr igetOutEdgesIterator( size_t vid )
	{
		return IGraph::IEdgeIteratorPtr( new WrapEdgeIterator< EdgeIterator, MyT >( * this, getEdgsBegId( vid ), getEdgsEndId( vid ) ) );
	}

	virtual void igetOutEdgesIterator( size_t vid, IGraph::IEdgeIterator & iter )
	{
		WrapEdgeIterator< EdgeIterator, MyT > * iterptr = dynamic_cast< WrapEdgeIterator< EdgeIterator, MyT > * >( & iter );
		if ( iterptr == NULL )
		{
			throw exceptions::BadGraphItemException();
		}
		* iterptr = WrapEdgeIterator< EdgeIterator, MyT >( * this, getEdgsBegId( vid ), getEdgsEndId( vid ) );
	}
	// TODO: develop BFS 4 virtual

public:
	void addEdge( const GrVertex & beg, const GrVertex & end, const EdgeAttributes & edgeAttrs = EdgeAttributes() )
	{
		size_t begVid = vert2num( beg );
		size_t endVid = vert2num( end );
		addVidEdge( begVid, endVid, edgeAttrs );
	}

	virtual void iaddEdge( size_t begVid, size_t endVid, const IGraph::IEdgeAttributesPtr & iattrs )
	{
//			throw exceptions::BadGraphItemException();
		// TODO: common style of local variables names attributes
		IEdgeAttributes * attrs = dynamic_cast< IEdgeAttributes * >( iattrs.get() );
		if ( attrs == NULL )
		{
			throw exceptions::BadGraphItemException();
		}
		addVidEdge( begVid, endVid, * attrs->get() );
	}

private:
	typedef EdgeAttributes * EdgeAttributesPtr;
	void addVidEdge( size_t begVid, size_t endVid, const EdgeAttributes & edgeAttrs )
	{
		EdgeAttributes & origAttrs = addVidSingleEdge( begVid, endVid, edgeAttrs );
		if ( Super::isBidirected )
		{
			EdgeAttributes & revertedAttrs = addVidSingleEdge( endVid, begVid, edgeAttrs );
			origAttrs.onBidirEdgeCreated( revertedAttrs, true );
			revertedAttrs.onBidirEdgeCreated( origAttrs, false );
		}
	}
	EdgeAttributes & addVidSingleEdge( size_t begVid, size_t endVid, const EdgeAttributes & edgeAttrs )
	{
		if ( k == destBuf.size() )
		{
			size_t edgesCapacity = destBuf.size();
			resizeStructure( edgesCapacity * 2 );
		}
		// TODO: !!!
		assert( k < destBuf.size() );
		dest[k] = endVid;
		nx[k] = st[begVid];
		st[begVid] = k;
		// TODO: name of edgeAttrs
		attributes[k] = attributesPool.construct( edgeAttrs );
		EdgeAttributes & result = * attributes[k];
		k++;
		return result;
	}
	void init()
	{
		k = 0;
		size_t vertexCount = Super::getVertexCount();
// TODO: !!!
		size_t edgesCount = vertexCount * 2;
		stBuf.resize( vertexCount, -1 );
		destBuf.resize( edgesCount );
		nxBuf.resize( edgesCount, -1 );
		attributesBuf.resize( edgesCount, NULL );

		buf2arrs();
	}
	void resizeStructure( size_t edgesCapacity )
	{
		if ( edgesCapacity < destBuf.size() )
		{
			return;
		}

		std::vector< int > destBackBuf = destBuf;
		int * destBack = & destBackBuf[0];
		std::vector< int > nxBackBuf = nxBuf;
		int * nxBack = & nxBackBuf[0];
		std::vector< EdgeAttributesPtr > attributesBackBuf = attributesBuf;
		EdgeAttributesPtr * attributesBack = & attributesBackBuf[0];

		destBuf.resize( edgesCapacity );
		nxBuf.resize( edgesCapacity );
		attributesBuf.resize( edgesCapacity, NULL );

		buf2arrs();

		std::copy( destBack, destBack + k, dest );
		std::copy( nxBack, nxBack + k, nx );
		std::copy( attributesBack, attributesBack + k, attributes );
	}
	void buf2arrs()
	{
		st = & stBuf[0];
		dest = & destBuf[0];
		nx = & nxBuf[0];
		attributes = & attributesBuf[0];
	}

public:
	std::vector< GrVertex > & getVertices()
	{
		return Super::vertices;
	}
	// TODO: bug on resize
	int k;
	std::vector< int > stBuf;
	std::vector< int > destBuf;
	std::vector< int > nxBuf;
	boost::object_pool< EdgeAttributes > attributesPool;
	std::vector< EdgeAttributesPtr > attributesBuf;
	int * st;
	int * dest;
	int * nx;
	EdgeAttributesPtr * attributes;
};

}
}
}

#endif /* COMPACTGRAPHTMPL_H_ */
